package java_thinking.unit_16.source;

/**
 * @Desc:   赋值填充方式 —- 一端挖坑一端填充
 *          结合 2.赋值填充方式-一端挖坑一端填充-图解.png
 *
 * @author: cww
 * @DateTime: 2019/4/23 20:33
 */

public class FillSort {
    public static void main(String[] args) {
        int[] a1 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        int[] a2 = {5,9,1,1,2,9,8,1,3,5,15,22,1,8};
        long begin = System.nanoTime();
        fillSort(a1);
        long end = System.nanoTime();
        System.out.println("fillSort: " + (end - begin));
        long begin1 = System.nanoTime();
        SingleSwapSort.deScanSwapSort(a2);
        long end1 = System.nanoTime();
        System.out.println("deScanSwapSort: " + (end1 - begin1));

    }

    public static void fillSort(int[] items) {
        fillSort(items, 0, items.length - 1);
    }

    public static void fillSort(int[] items, int start, int end) {
        if (start < end) {
            int pivot = items[start];
            int i = start,j = end;
            while (i < j) {
                while (i < j && items[j] > pivot) {
                    j--;
                }
                //找到比pivot小的
                items[i] = items[j];
                while (i < j && items[i] <= pivot) {
                    i++;
                }
                //找到比pivot大的
                items[j] = items[i];
            }
            // 相遇后i == j，填入pivot
            items[i] = pivot;
            fillSort(items,start,i-1);
            fillSort(items,i+1,end);
        }
    }

    public static void swap(int[] items, int i, int j) {
        int tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }
}
